class ListNode {
    val: number;
    next: ListNode | null;

    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
// 反转链表
function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr: ListNode | null = head;
    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

// 链表中环的检测
function hasCycle(head: ListNode | null): boolean {

    if (head === null || head.next === null) {
        return false;
    }
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;

    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow!.next;
        if (slow === fast) {
            return true;
        }
    }
    return false;
}

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}
// 二叉树的最大深度
function maxDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

// 二叉树的层次遍历
function levelOrder(root: TreeNode | null): number[][] {
    if (root === null) return [];
    let queue: TreeNode[] = [root];
    let result: number[][] = [];
    while (queue.length) {
        const size = queue.length;
        const level: number[] = [];
        for (let i = 0; i < size; i++) {
            const current: TreeNode = queue.shift() as TreeNode;
            level.push(current.val);
            if (current.left) {
                queue.push(current.left);
            }
            if (current.right) {
                queue.push(current.right);
            }
        }
        result.push(level);
    }
    return result;
}

// 最长递增子序列
function lengthOfLIS(nums: number[]): number {
    // 处理空数组的情况
    if (nums.length === 0) {
        return 0;
    }

    // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    // 初始时，每个元素自身至少可以构成长度为1的递增子序列
    const dp: number[] = new Array(nums.length).fill(1);

    // 遍历数组中的每个元素
    for (let i = 1; i < nums.length; i++) {
        // 对于当前元素 nums[i]，检查所有在它之前的元素 nums[j]
        for (let j = 0; j < i; j++) {
            // 如果当前元素大于之前的某个元素，说明可以形成递增关系
            if (nums[i] > nums[j]) {
                // 更新 dp[i]：比较当前值和以 nums[j] 结尾的子序列长度加1
                // 取较大值作为新的 dp[i]
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    // 返回dp数组中的最大值，即整个数组的最长递增子序列长度
    return Math.max(...dp);
}
/**
 * 零钱兑换问题（动态规划解法）
 * 问题：给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额所需的最少的硬币个数
 * 如果无法凑成总金额，返回 -1
 * 
 * 思路：使用动态规划，dp[i] 表示凑成金额 i 所需的最少硬币数
 * 
 * 状态转移方程：
 * dp[i] = min(dp[i], dp[i - coin] + 1) 对于所有 coin <= i
 * 含义：对于金额 i，尝试使用每种硬币 coin，如果 coin <= i，
 *       则可以通过 dp[i - coin] + 1 来得到 dp[i]（使用一枚 coin 面额的硬币）
 * 
 * 时间复杂度：O(amount * coins.length)
 * 空间复杂度：O(amount)
 */
function coinChange(coins: number[], amount: number): number {
    // dp[i] 表示凑成金额 i 所需的最少硬币数
    // 初始化为最大值，表示暂时无法凑成
    const dp: number[] = new Array(amount + 1).fill(Number.MAX_SAFE_INTEGER);

    // 边界条件：凑成金额 0 需要 0 枚硬币
    dp[0] = 0;

    // 从金额 1 开始，逐步计算到 amount
    for (let i = 1; i <= amount; i++) {
        // 尝试使用每种面额的硬币
        for (let j = 0; j < coins.length; j++) {
            const coin = coins[j];
            // 如果当前硬币面额 <= 目标金额，可以使用这枚硬币
            if (coin <= i) {
                // 状态转移：dp[i] = min(当前值, 使用这枚硬币后的硬币数)
                // dp[i - coin] + 1 表示：凑成 (i - coin) 的最少硬币数 + 1枚当前硬币
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果 dp[amount] 仍然是最大值，说明无法凑成，返回 -1
    // 否则返回最少硬币数
    return dp[amount] === Number.MAX_SAFE_INTEGER ? -1 : dp[amount];
}
// 最长无重复字符子串
function lengthOfLongestSubstring(s: string): number {
    // 使用 Map 存储字符和其最新出现的位置
    const charMap = new Map<string, number>();
    let maxLength = 0;
    let left = 0; // 滑动窗口的左边界

    for (let right = 0; right < s.length; right++) {
        const currentChar = s[right];

        // 如果字符已经在窗口中，移动左边界
        if (charMap.has(currentChar) && charMap.get(currentChar)! >= left) {
            left = charMap.get(currentChar)! + 1;
        }

        // 更新字符的最新位置
        charMap.set(currentChar, right);

        // 更新最大长度
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

// 寻找两个正序数组的中位数
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const merged = nums1.concat(nums2).sort((a, b) => a - b);
    const mid = Math.floor(merged.length / 2);
    return merged.length % 2 === 0 ? (merged[mid - 1] + merged[mid]) / 2 : merged[mid];
}
// 二分法
function findMedianSortedArrays2(nums1: number[], nums2: number[]): number {
    // 确保 nums1 是较短的数组，这样我们可以减少二分查找的范围
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }
    const m = nums1.length;
    const n = nums2.length;
    const totalLength = m + n;
    const halfLength = Math.floor((totalLength + 1) / 2); //预期左边的元素个数

    let left = 0;
    let right = m;

    while (left <= right) {
        // 在 nums1 中找到一个分割点 i
        const i = Math.floor((left + right) / 2);
        // 根据 i 计算 nums2 中的分割点 j
        const j = halfLength - i;

        // 计算分割线两边的值
        const nums1Left = i > 0 ? nums1[i - 1] : -Infinity;
        const nums1Right = i < m ? nums1[i] : Infinity;
        const nums2Left = j > 0 ? nums2[j - 1] : -Infinity;
        const nums2Right = j < n ? nums2[j] : Infinity;

        // 检查：所有左边元素 ≤ 所有右边元素
        if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
            // 找到正确的分割线
            if (totalLength % 2 === 1) {
                // 总长度为奇数，中位数是左边最大值
                return Math.max(nums1Left, nums2Left);
            } else {
                // 总长度为偶数，中位数是左边最大值和右边最小值的平均值
                return (
                    (Math.max(nums1Left, nums2Left) +
                        Math.min(nums1Right, nums2Right)) /
                    2
                );
            }
            // 调整二分查找范围;
        } else if (nums1Left > nums2Right) {
            // 分割线太靠右了，向左移动
            right = i - 1;
        } else {
            // 分割线太靠左了，向右移动
            left = i + 1;
        }
    }
    throw new Error('Input arrays are not sorted');
}
// 两数之和
export function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        const index = nums.indexOf(target - nums[i]);
        if (index > -1 && index !== i) {
            return [i, index];
        }
    }
    return [];
}
/**
 * 有效的括号（栈解法）
 * 问题：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效
 * 有效字符串需满足：
 * 1. 左括号必须用相同类型的右括号闭合
 * 2. 左括号必须以正确的顺序闭合
 * 3. 每个右括号都有一个对应的左括号
 * 
 * 思路：使用栈（Stack）数据结构
 * - 遇到左括号时，将其入栈
 * - 遇到右括号时，检查栈顶元素是否是对应的左括号
 *   - 如果是，则出栈（匹配成功）
 *   - 如果不是或栈为空，则返回 false（匹配失败）
 * - 最后检查栈是否为空，空则说明所有括号都匹配成功
 * 
 * 时间复杂度：O(n)，n 为字符串长度
 * 空间复杂度：O(n)，最坏情况下栈中存储所有左括号
 */
function isValid(s: string): boolean {
    // 使用栈存储左括号
    const stack: string[] = [];

    // 建立右括号到左括号的映射关系，方便快速查找匹配的左括号
    const map: { [key: string]: string } = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    // 遍历字符串中的每个字符
    for (let i = 0; i < s.length; i++) {
        const currentChar = s[i];

        // 如果是左括号，入栈
        if (currentChar === '(' || currentChar === '[' || currentChar === '{') {
            stack.push(currentChar);
        }
        // 如果是右括号，需要与栈顶的左括号匹配
        else if (currentChar === ')' || currentChar === ']' || currentChar === '}') {
            // 弹出栈顶元素（如果栈为空，pop() 返回 undefined）
            const lastChar = stack.pop();

            // 检查栈顶的左括号是否与当前右括号匹配
            // map[currentChar] 获取当前右括号对应的左括号
            // 如果不匹配或栈为空（lastChar 为 undefined），返回 false
            if (map[currentChar] !== lastChar) {
                return false;
            }
        }
    }

    // 如果栈为空，说明所有括号都匹配成功；否则还有未匹配的左括号
    return stack.length === 0;
}